Patience Sorting LIS
Используется бинарный поиск для поддержания массива минимальных хвостов.
int lengthOfLIS(vector<int>& nums) {
vector<int> tails;
for (int n : nums) {
auto it = lower_bound(tails.begin(), tails.end(), n);
if (it == tails.end()) {
tails.push_back(n); // Extend LIS
} else {
*it = n; // Improve existing tail
}
}
return tails.size();
}
def lengthOfLIS(nums):
tails = []
for n in nums:
idx = bisect_left(tails, n)
if idx == len(tails):
tails.append(n)
else:
tails[idx] = n
return len(tails)